

struct sstable_index
{

	typedef std::map<const key_wrapper*, fs::offset_t,
			 lt_key_wrapper> index_map_type;

	sstable_index(const dynamic_buffer &key_data,
		      const dynamic_buffer &offset_data)
		: m_index()
		, m_key_buffer(key_data)
		, m_offset_buffer(offset_data) {}

	index_map_type m_index;

	// load index from buffer
	void load_index(const const_buffer &data) {
		
	}
};

template<typedef allocT = std::allocator<char> >
struct dynamic_buffer
{
	typedef boost::asio::mutable_buffer mutable_buffer;
	typedef boost::asio::const_buffer const_buffer;

	typedef std::vector<mutable_buffer> mutable_buffer_sequence;
	typedef std::vector<const_buffer> const_buffer_sequence;

	typedef boost::asio::detail::consuming_buffers<mutable_buffer, mutable_buffer_sequence> const_consuming_buffers;
	typedef boost::asio::detail::consuming_buffers<mutable_buffer, mutable_buffer_sequence> mutable_consuming_buffers;

	typedef typename Alloc::template rebind< boost::shared_array<char> >::other vector_alloc_type;

	size_t put(const_buffer data) {
		size_t bytes_copied = 0;
		while(buffer_size(data) > 0)
		{
			ensure_has_space();
			const size_t bytes_to_copy = (std::min)(buffer_size(data),
								buffer_size(m_left_buffer));
			std::memncpy(buffer_cast<char*>(m_left_buffer),
				     buffer_cast<const char*>(data),
				     bytes_to_copy);
			
			data = data + bytes_to_copy;
			m_left_buffer = m_left_buffer + bytes_to_copy;
			bytes_copied += bytes_to_copy;
		}
		return bytes_copied;
	}

	template<typename ConstBufferSequence>
	size_t put(const ConstBufferSequence &data) {
		for(ConstBufferSequence::const_iterator
			    iter=data.begin(), end=data.end();
		    iter != end; ++iter)
		{
			put(*iter);
		}
		return copied;
	}

	size_t get(mutable_buffer buffer) const {
		size_t size = buffer_size(buffer);
		buffer_sequence::iterator
			iter = m_buffers.begin(),
			last = iter + (m_buffers.size() - 1);
		// whole trunk copy
		for(; (buffer_size(buffer) >= m_trunk_size) &&
			    (iter != last);
		    ++iter)
		{
			std::memncpy(buffer_cast<char*>(buffer),
				     iter->get(),
				     m_trunk_size);
			buffer = buffer + m_trunk_size;
		}
		// less copy
		if (buffer_size(buffer) > 0)
		{
			size_t to_copy = buffer_size(buffer);
			if (iter == last)
			{
				to_copy = (std::min)(m_trunk_size - buffer_size(m_left_buffer),
						     to_copy);
			}
			if(to_copy != 0)
			{
				std::memncpy(buffer_cast<char*>(buffer),
					     iter->get(),
					     to_copy);
				buffer = buffer + to_copy;
			}
		}
		return size - buffer_size(buffer);
	}

	void clear() {
		m_left_buffer = mutable_buffer();
		m_buffers.clear();
	}

	size_t size() const {
		return m_trunk_size * m_buffers.size() - buffer_size(m_left_buffer);
	}

	// 合并多个trunk，调整trunk_size到当前容量大小
	const_buffer merge() {
		if(m_buffers.size() > 1) // merge
		{
			size_t old_trunk_size = m_trunk_size;
			m_trunk_size = old_trunk_size * m_buffers.size(); // update trunk size
			boost::shared_array<char> new_trunk = allocate_trunk(); // allocate with new size
			mutable_buffer new_buffer(new_trunk.get(), m_trunk_size);
			new_buffer = new_buffer + this->get(new_buffer);
			assert(buffer_size(new_buffer) == buffer_size(m_left_buffer));

			this->clear(); // release old memory
			m_buffers.push_back(new_trunk);
			m_left_buffer = new_buffer;
		}
		return const_buffer(m_buffers.back().get(),
				    m_trunk_size - buffer_size(m_left_buffer));
	}
	
	// template<typename MutableBufferSequence>
	// size_t get(const MutableBufferSequence &buffers) const {
	// 	mutable_consuming_buffers tmp(buffers);
	// 	size_type copied = 0;
	// 	while(tmp.begin() != tmp.end())
	// 	{
	// 		const mutable_buffer &buf = tmp.begin();
	// 		const size_type bytes = (std::min)();
	// 	}
	// }

	const_buffer_sequence buffers() {
		const_buffer_sequence buffers;
		foreach(boost::shared_array<char> elem, m_buffers)
		{
			buffers.push_back(const_buffer(elem.get(), m_trunk_size));
		}
		boost::asio::buffer_size(buffers.back()) = m_trunk_size - m_left_space;
	}

	dynamic_buffer(const size_type trunk_size,
		       const allocator_type &alloc = allocator_type())
		: m_trunk_size(trunk_size)
		, m_buffers(alloc)
		, m_left_buffer()
		, m_alloc(alloc) {}

	enum
	{
		MINIMAL_TRUNK_SIZE = 1024 * 512, // 512K
		MAX_TRUNK_NUMBER = 9		 // 如果＞该值，则合并
	};

protected:
	void ensure_has_space() {
		if (buffer_size(m_left_buffer) == 0)
		{
			if (m_buffers.size() > MAX_TRUNK_NUMBER)
			{
				this->merge();
			}
			boost::shared_array<char> trunk = allocate_trunk();
			m_buffers.push_back(trunk);
			m_left_buffer = mutable_buffer(trunk.get(), m_trunk_size);
		}
	}

	boost::shared_array<char> allocate_trunk() {
		return boost::shared_array<char>(m_alloc.allocate(m_trunk_size),
					       boost::bind(this, &deallocate_trunk));
	}

	void deallocate_trunk(char *trunk) {
		m_alloc.deallocate(trunk, m_trunk_size);
	}

private:
	std::vector<boost::shared_array<char>, vector_alloc_type> m_buffers;
	size_type m_trunk_size;
	mutable_buffer m_left_buffer;

	allocator_type m_alloc;
};

template<typename allocT = std::allocator<char> >
struct heap_buffer
{
	std::vector<T*> m_heap_buffers;
	const size_t m_trunk_size;

	T *m_cur_buffer;
	size_t m_cur_size;

	allocT m_alloc;

	heap_buffer(size_t trunk_size)
		: m_trunk_size(trunk_size)
		, m_cur_buffer(0)
		, m_cur_size(0) {}

	~heap_buffer() {
		for(std::vector<T*>::iterator
			    iter=m_heap_buffers.begin(),
			    end=m_heap_buffers.end();
		    iter != end; ++iter)
		{
			m_alloc.deallocate(*iter, m_trunk_size);
		}
	}

	void fill(const char *data, size_t size) {
		if (m_cur_size == m_trunk_size)
		{
			m_cur_buffer = 0;
			m_cur_size = 0;
		}
		if (! m_cur_buffer)
		{
			m_cur_buffer = m_alloc.allocate(m_trunk_size);
			m_heap_buffers.push_back(m_cur_buffer);
			m_cur_size = 0;
		}
		while(size > (m_trunk_size - m_cur_size))
		{
			memncpy(m_cur_buffer, data, m_trunk_size - m_cur_size);
			size -= (m_trunk_size - m_cur_size);
			
			m_cur_buffer = m_alloc.allocate(m_trunk_size);
			m_heap_buffers.push_back(m_cur_buffer);
			m_cur_size = 0;
		}
		while (size > 0)
		{
			memncpy(m_cur_buffer, data, size);
			size = 0;
		}
	}
};

template<typename allocT = std::allocator<char>,
	 unsigned int stack_size>
struct stack_buffer
{
	char m_stack_buffer[stack_size];
	std::vector<char, allocT> m_heap_buffers;

	char *m_cur_buffer;
	size_t 	m_cur_pos;
	
	void put(char* data, size_t size) {
		size_t left_size = size;
		if ((size + m_data_size) > stack_size)
		{
			memncpy(m_stack_buffer,
				data,
				stack_size - m_data_size);
			left_size = size - (stack_size - m_data_size);
			m_data_size = stack_size;
		}
		if (left_size > 0)
		{
			if (m_heap_buffer.empty())
			{
				std::pair<boost::shared_array<char>,
					size_t> buffer(new char[stack_size],
						       0);
				m_heap_buffer.push_back(buffer);
			}
			memncpy(buffer.first.get(),
				data + (size - left_size),
				left_size);
			buffer.second = left_size;
		}
	}
		
};
